package madixin.t347;

import java.util.*;

class Solution {
    //freqMap,堆排序
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int n : nums) {
            freqMap.put(n, freqMap.getOrDefault(n, 0) + 1);
        }

        for (Integer key : freqMap.keySet()) {
            System.out.println(key + ":" + freqMap.get(key));
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return freqMap.get(o1) - freqMap.get(o2);
            }
        });

        for (Integer key : freqMap.keySet()) {
            if (queue.size() < k) {
                queue.add(key);
            } else if (freqMap.get(key) > freqMap.get(queue.peek())) {
                queue.poll();
                queue.add(key);
            }
        }

        List<Integer> res = new LinkedList<>();
        while (!queue.isEmpty()) {
            res.add(queue.poll());
        }
        return res;
    }


    //freqMap,桶排序
    public List<Integer> topKFrequent1(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int n : nums) {
            freqMap.put(n, freqMap.getOrDefault(n, 0) + 1);
        }

        for (Integer key : freqMap.keySet()) {
            System.out.println(key + ":" + freqMap.get(key));
        }

        List<Integer>[] bucket = new LinkedList[nums.length + 1];
        for (Integer key : freqMap.keySet()) {
            int frequency = freqMap.get(key);
            if (bucket[frequency] == null) {
                List<Integer> list = new LinkedList();
                list.add(key);
                bucket[frequency] = list;
            } else {
                bucket[frequency].add(key);
            }
        }

        List<Integer> res = new LinkedList<>();
        for (int i = bucket.length - 1; i > 0; i--) {
            if (bucket[i] == null) {
                continue;
            } else {
                int size = bucket[i].size();
                if (res.size() + size < k) {
                    res.addAll(bucket[i]);
                } else {
                    res.addAll(bucket[i].subList(0, k - res.size()));
                    break;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2));
    }

}